#include "sorter.h"
/**
 * @brief myinsertSorter 我的插入排序
 * @param arr
 * @param len
 * @return
 */
int myinsertSorter(int* arr,int len){
    //第一遍不用
    for(int i=1;i<len;i++){
        int tmp=arr[i];
        int j=i-1;
        // 0 1 2 [0.4] 4 5
        for(;j>=0&&(arr[j]>tmp);--j){
            arr[j+1]=arr[j];
        }
        arr[j+1]=tmp;
    }

    for(int i=0;i<len;i++){
        printf("%d ",arr[i]);
    }
    return 0;
}

/**
 * @brief shellSort 希尔排序
 * @param arr
 * @param len
 * @return
 */
int shellSort(int* arr,int len){

    int gap=len;
    do{
        //分组大小为gap大小
        gap=gap/3+1;//O(n*1.3)
        //决定一共有多少个分组
        for(int k=0;k<gap;++k){

            //开始最表为xxx的分组，以间隙为xxx
            printf("start idx:%d groups with gap:%d\n",k,gap);
            //他会是这样的
            printf("and it would be like:");
            for(int x=k;x<len;x+=gap){
                printf("%d ",x);
            }
            // 0 1 2 3 4 5 6 7
            for(int i=k+gap;i<len;i+=gap){
                printf("\n%d ",i);
                int tmp=arr[i];
                int j=i-gap;
                // 0 1 2 [0.4] 4 5
                printf("\nprevious was:");
                for(;j>=k&&(arr[j]>tmp);j-=gap){
                    printf("%d ,",j);
                    printf("\nprev val:%d currentVal:%d",arr[j],tmp);
                    arr[j+gap]=arr[j];
                }
                arr[j+gap]=tmp;
            }
            printf("\n");
        }

    }while(gap>1);

    for(int i=0;i<len;i++){
        printf("%d ",arr[i]);
    }
    return 0;
}

/**
 * @brief merge 归并排序
 * @param a 基础数组
 * @param first 第一号元素
 * @param mid 中位元素
 * @param last 末尾元素
 * @param temp 临时数组
 * @return
 */
int merge(int a[],int first,int mid,int last,int temp[]){
    int leftStart=first;
    int leftEnd=mid;
    int rightStart=mid+1;
    int rightEnd=last;
    int length=0;
    int i=leftStart;
    int j=rightStart;
    while (i<=leftEnd&&j<=rightEnd) {
        if(a[i]<a[j]){
            temp[length++]=a[i++];
        }else{
            temp[length++]=a[j++];
        }
    }

    while(i<=leftEnd){
        temp[length++]=a[i++];
    }

    while(j<=rightEnd){
        temp[length ++]=a[j++];
    }
    //最后，还需要将临时中已经拍好序列的拷贝到a中，让a对应部分称为有序的序列。
    for(int i=0;i<length;i++){
        a[leftStart+i]=temp[i];
    }
    return 0;
}
/**
 * @brief mergeSort 归并排序
 * @param arr
 * @param len
 * @return
 */
int mergeSort(int *arr,int first,int last,int temp[]){
    if(first<last){
        int mid=(last+first)/2;
        mergeSort(arr,first,mid,temp);
        mergeSort(arr,mid+1,last,temp);
        merge(arr,first,mid,last,temp);
    }
    return 0;
}

/**
 * @brief mergeSortExt 归并排序的有点
 * 复杂度O(N*logN) 是一种稳定的排序算法
 * @param arr
 * @param size
 * @return
 */
int mergeSortExt(int* arr,int size){
    int temp[size];
    mergeSort(arr,0,size-1,temp);
    for(int i=0;i<size;i++){
        printf("%d ",arr[i]);
    }
}
